\section{矩形覆盖(P1034)}
\subsection{题目描述}
在平面上有n个点(n≤50)，每个点用一对整数坐标表示。
例如：当 n=4时，4个点的坐标分另为：p1​(1,1)，p2​(2,2)，p3​(3,6)，P4​(0,7)，见下图。

\begin{figure}[htbp]
\centering
\includegraphics[scale=0.8]{questions/fig/p1034}
\caption{矩形覆盖}
\end{figure}

这些点可以用k矩形(1≤k≤4)全部覆盖，矩形的边平行于坐标轴。
当k=2时，可用如图二的两个矩形s1,s2​ 覆盖，s1,s2 面积和为4。
问题是当n个点坐标和k给出后，怎样才能使得覆盖所有点的k个矩形的面积之和为最小呢？
约定：覆盖一个点的矩形面积为0；覆盖平行于坐标轴直线上点的矩形面积也为0。各个矩形必须完全分开（边线与顶点也都不能重合）。

\subsection{输入}
$n\quad k$\\
$x_1\quad y_1$\\
$x_2\quad y_2$\\
... ...\\
$x_n\quad y_n$​ ($\leq x_i,y_i \leq 500$)

\subsection{输出}
输出至屏幕。格式为：\\
1个整数，即满足条件的最小的矩形面积之和。

\subsection{样例}
\textbf{输入样例}
\begin{lstlisting}
4 2
1 1
2 2
3 6
0 7
\end{lstlisting}
%\subsection{提示}
\textbf{输出样例}
\begin{lstlisting}
4
\end{lstlisting}

\subsection{分析}
本题难点有两个：1、不能用贪心策略，只能搜索；2、搜索路径的设计。

假设k=3，我们先把整个图形用两个矩形覆盖，这两个矩形是所有其他组合中面积最小的。
如果基于这两个矩形再来拆分出第三个，可能得不到最优解。必须进行完全搜索比较。
也就是说切第一刀的局部最优解并不一定是全局最优解。

搜索路径分为两级：首先把一个矩形分为两个，然后继续对这两个矩形进行递归切分。
这两个矩形里面分别需要切分出：i和nr\_part-i个矩形，对i进行循环。

先把点按照横坐标排序，先纵向切分矩形，切分的时候以每个点的横坐标为切口。
先把点按照纵坐标排序，先横向切分矩形，切分的时候以每个点的纵坐标为切口。

计算矩形面积的时候，首先找到矩形覆盖的所有点，然后根据这些点坐标把矩形的外边框
缩小为刚好能够覆盖所有点。

\subsection{代码}
\begin{lstlisting}
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std; 

#define INF 0x7f7f7f7f

struct point_s {
	int x, y; 
}; 

vector <point_s> ap, hp, vp; 
int n, k; 

struct rect_s {
	int x0, y0, x1, y1; 
	int min_x, max_x, min_y, max_y; 
	int size; 
	rect_s() {
		min_x = min_y = INF; 
		max_x = max_y = 0; 
		size = INF; 
	}
	void set_frame(int _x0, int _y0, int _x1, int _y1) {
		x0 = _x0; 
		y0 = _y0; 
		x1 = _x1; 
		y1 = _y1; 
		size = INF; 
	}
	int get_size(void) {
		int chs = 0; 
		if (size!=INF) {
			return size; 
		}
		for (unsigned i=0; i<ap.size(); i++) {
			point_s &p = ap[i]; 
			if (p.x<=x0 || p.x>x1 || p.y<=y0 || p.y>y1) {
				continue; 
			}
			chs ++; 
			max_x = max(max_x, p.x); 
			max_y = max(max_y, p.y); 
			min_x = min(min_x, p.x); 
			min_y = min(min_y, p.y); 
		}
		size = (max_x - min_x) * (max_y - min_y); 
		size = chs>0 ? size : 0; 
		return size; 
	}
};

bool cmp_h(point_s &a, point_s &b)
{
	return a.x<b.x; 
}

bool cmp_v(point_s &a, point_s &b)
{
	return a.y<b.y; 
}

int split(rect_s &r, int nr_parts)
{
	int size, b_size, a_size, min_size = INF; 

	if (nr_parts==1) {
		return r.get_size();
	}

	for (int np=1; np<nr_parts; np++) {
		for (int i=0; i<n; i++) {
			point_s &p = hp[i]; 
			rect_s a, b; 
			if (p.x<=r.x0 || p.x>r.x1) {
				continue; 
			}
			a.set_frame(r.x0, r.y0, p.x, r.y1); 
			a_size = split(a, np); 
			b.set_frame(p.x, r.y0, r.x1, r.y1); 
			b_size = split(b, nr_parts-np); 
			size = a_size + b_size; 
			min_size = min(min_size, size); 
		}
		for (int i=0; i<n; i++) {
			point_s &p = vp[i]; 
			rect_s a, b; 
			if (p.y<=r.y0 || p.y>r.y1) {
				continue; 
			}
			a.set_frame(r.x0, r.y0, r.x1, p.y); 
			a_size = split(a, np); 
			b.set_frame(r.x0, p.y, r.x1, r.y1); 
			b_size = split(b, nr_parts-np); 
			size = a_size + b_size; 
			min_size = min(min_size, size); 
		}
	}
	return min_size; 
}

int main()
{
	rect_s rr, a, b, aa, ab, ba, bb;  
	int res; 
	
	cin>>n>>k; 
	for (int i=0; i<n; i++) {
		point_s p; 
		cin>>p.x>>p.y; 
		ap.push_back(p); 
		hp.push_back(p); 
		vp.push_back(p); 
	}
	sort(hp.begin(), hp.end(), cmp_h); 
	sort(vp.begin(), vp.end(), cmp_v); 

	rr.set_frame(-1, -1, 501, 501); 
	res = split(rr, k); 
	cout<<res<<"\n"; 
	return 0; 
}
\end{lstlisting}



